/*
 * doublePQi.java
 *
 * Created on 4 de enero de 2007, 10:32 AM
 */

package networkFlow;

/**
 *
 * @author tavobula
 */
public class intPQi {
    private int N;
    private int d=3;
    private int[] a;
    private int[] pq, qp;
    
    private boolean less(int i, int j){
        return a[pq[i]]<a[pq[j]];
    }
    
    private void exch(int i, int j){
        int t=pq[i];
        pq[i]=pq[j];
        pq[j]=t;
        qp[pq[i]]=i;
        qp[pq[j]]=j;
    }
    
    private void swim(int k){
        while(k>1 && less(k,(k+d-2)/d)){
            exch(k,(k+d-2)/d);
            k=(k+d-2)/d;
        }
    }
    
    private void sink(int k, int N){
        int j;
        while((j=d*(k-1)+2)<=N){
            for(int i=j+1;i<j+d && i<=N;++i)
                if(less(i,j))j=i;
            if(!(less(j,k))) break;
            exch(k,j);
            k=j;
        }
    }
    
    
    /** Creates a new instance of doublePQi */
    public intPQi(int maxN, int [] a) {
        this.a=a;
        this.N=0;
        pq=new int[maxN+1];
        qp=new int[maxN+1];
        for(int i=0;i<=maxN;++i){
            pq[i]=0;
            qp[i]=0;
        }
    }
    
    boolean empty(){
        return N==0;
    }
    
    void insert(int v){
        pq[++N]=v;
        qp[v]=N;
        swim(N);
    }
    
    int getmin(){
        exch(1,N);
        sink(1,N-1);
        return pq[N--];
    }
    
    void lower(int k){
        swim(qp[k]);
    }
}
